class UGRAPH{NTP} < $UGRAPH{NTP} |
---|
**** | For now, call this UGRAPH since we have no other graph implementations. A basic undirected graph implemented with a hash table from nodes to neighbors. This implementation mainly specifies the access routines. |
$UGRAPH{_} | $RO_UGRAPH{_} | $GRAPH{_,_} | $STR | $ELT{_} | $ELT | UGRAPH_INCL{_} | COMPARE{_} |
add_node(n: NTP) |
---|
**** | Add a node "n".
_ Technical detail: Since the node index for "n" is the same as the node for this particular implementation, there is no need to return a value. Note that this function is not in the graph abstraction |
add_node(n: NTP):NTP |
---|
**** | Replaces an existing node that is the same as "n" This function is guaranteed to return the same node, "n" though this is not true of graph implementations in general |
add_node: NTP |
---|
**** | Add a new node and return the index |
adjacent(n: NTP): SET{NTP} .. Included as adjacent |
---|
are_connected(n1,n2: NTP): BOOL .. Included as are_connected |
---|
**** | Return true if there exists a path from n1 to n2 |
connect(n1,n2: NTP) |
---|
**** | Connect n1 and n2. Add the nodes if they do not exist |
connect(e: UEDGE{NTP}) .. Included as connect |
---|
copy: SAME |
---|
create(node_gen: $SUCC_STREAM{NTP}): SAME |
---|
**** | Create a new ugraph. Store "node_gen" as a generator of nodes, so that when "add_node: NTP" is called it can generate unique new nodes. |
create: SAME |
---|
**** | All the data structures can be initialized with void |
delete_node(n: NTP) |
---|
**** | Delete a node from the graph, and all its accompanying edges |
delete_reflexive_edges .. Included as delete_reflexive_edges |
---|
**** | Delete all reflexive edges from the graph |
dfs_apply(n: NTP,wk:ROUT{NTP}) .. Included as dfs_apply |
---|
**** | Apply the pre visit work "wk" to nodes in df order. Non recursive |
dfs_apply(n: NTP,prewk:ROUT{NTP},postwk:ROUT{UEDGE{NTP}}) .. Included as dfs_apply |
---|
**** | Perform pre work before visiting a node and perform postwk on the way back up each edge Recursive version of dfs (much simpler to code) Here postwork is applied to *all* edges, including back edges |
difference(g:$UGRAPH{NTP}): $UGRAPH{NTP} .. Included as difference |
---|
disconnect(n1,n2: NTP) |
---|
**** | Deletes the edge between n1 and n2 if it exists |
disconnect(e: UEDGE{NTP}) .. Included as disconnect |
---|
edges: SET{UEDGE{NTP}} .. Included as edges |
---|
equals(g: $RO_UGRAPH{NTP}): BOOL .. Included as equals |
---|
**** | Check that nodes and edges are the same Very inefficient n^2 version - sort for nlogn version |
has(n: NTP): BOOL .. Included as has |
---|
has_edge(first,second: NTP): BOOL .. Included as has_edge |
---|
has_edge(e: UEDGE{NTP}):BOOL .. Included as has_edge |
---|
has_node(n: NTP): BOOL .. Included as has_node |
---|
has_same_nodes(g: $RO_UGRAPH{NTP}): BOOL .. Included as has_same_nodes |
---|
induced_subgraph(v: $SET{NTP}): $UGRAPH{NTP} .. Included as induced_subgraph |
---|
**** | Generate a subgraph which is induced by the edges "v". |
is_empty: BOOL .. Included as is_empty |
---|
is_identical(g: SAME): BOOL |
---|
**** | Check whether the two graphs have the same nodes, edges in the same order |
n_adjacent(n: NTP): INT |
---|
n_edges: INT .. Included as n_edges |
---|
n_nodes: INT |
---|
n_reachable_from(n: NTP): INT .. Included as n_reachable_from |
---|
new_edge(n1,n2: NTP): UEDGE{NTP} |
---|
node_depths(n: NTP,map:$MAP{NTP,INT}) .. Included as node_depths |
---|
**** | map should be inout, but this will work for now Do a bfs and return depths of each node |
nodes: SET{NTP} .. Included as nodes |
---|
permute_nodes(new_positions: $MAP{NTP,INT}) |
---|
**** | Permute the nodes of the graph so that they will be yielded in the order expressed by "new_positions" |
reachable_from(n: NTP): SET{NTP} .. Included as reachable_from |
---|
**** | Returns the set of nodes reachable from "n" |
roots: SET{NTP} .. Included as roots |
---|
**** | Returns a list of "representative" nodes from which the whole graph is reachable. With inout args, also return a mapping from nodes to the appropriate representative nodes (i.e. seen) |
size: INT .. Included as size |
---|
sort |
---|
**** | Reduce the graph to a canonical form based on the sorting order of nodes and edges |
str(f: ROUT{NTP}:STR): STR .. Included as str |
---|
**** | Print out the graph using the bound routine "f" for the nodes |
str: STR .. Included as str |
---|
test_edge(s,t: NTP): BOOL |
---|
test_node(n: NTP): BOOL |
---|
to_difference(g: $UGRAPH{NTP}) .. Included as to_difference |
---|
to_transitive_closure .. Included as to_transitive_closure |
---|
**** | Convert the graph to it's transitive closure For a non-destructive version, first make a copy |
to_union(g: $UGRAPH{NTP}) .. Included as to_union |
---|
union(g: $UGRAPH{NTP}): $UGRAPH{NTP} .. Included as union |
---|
adjacent!(once n: NTP): NTP |
---|
bfs!(once n: NTP): NTP .. Included as bfs! |
---|
**** | Return all nodes reachable from "n" in bf order |
dfs!(once n: NTP): NTP .. Included as dfs! |
---|
**** | Return all nodes reachable from "n" in df order |
edge!: UEDGE{NTP} |
---|
**** | Return all edges in the graph. A problem, since we represent edges in both directions. We might want to either maintain a hash table of edges already seen or generate a matching or something of the sort. Or can use some arbitrary test to choose one or the other. such as lt For now, use a set which holds all nodes for which all edges have been yielded edges yielded |
elt!: NTP .. Included as elt! |
---|
filter_edge!(once .. Included as filter_edge! |
---|
**** | Return a set of edge tuples that are true for test "et" |
filter_node!(once .. Included as filter_node! |
---|
**** | Return the set of all nodes in g that satisfy the node test "nt" |
node!: NTP |
---|
reachable_from!(once n: NTP): NTP .. Included as reachable_from! |
---|
**** | Returns successive nodes reachable from "n" using dfs |
add_neighbor(n1,n2: NTP) |
---|
check_node(n: NTP,routine_name: STR): BOOL |
---|
dfs_rec(seen:FSET{NTP},n:NTP,bef:ROUT{NTP},aft:ROUT{UEDGE{NTP}}) .. Included as dfs_rec |
---|
**** | Recursive depth first search, when both pre and postwork must be done. Seen holds the list of nodes already seen |
elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
---|
**** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
elt_hash(e:ETP):INT .. Included as elt_hash |
---|
**** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
---|
**** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
elt_nil: ETP .. Included as elt_nil |
---|
**** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
---|
neighbor_list(n1:NTP):FLIST{NTP} |
---|
attr neighbor_map: FMAP{NTP,FLIST{NTP}}; |
---|
**** | holds mappings from each node to all it's neighbors |
attr neighbor_map: FMAP{NTP,FLIST{NTP}}; |
---|
**** | holds mappings from each node to all it's neighbors |
attr node_generator: $SUCC_STREAM{NTP}; |
---|
**** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
attr node_generator: $SUCC_STREAM{NTP}; |
---|
**** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
attr node_list: FLIST{NTP}; |
---|
attr node_list: FLIST{NTP}; |
---|
node_str(n: NTP): STR .. Included as node_str |
---|